package slidingWindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.function.BiFunction;

public class slidingWindowTest {
    public static void main(String[] args) {
        // Checker.maxSumChecker(Solution::maxSum, 10, 10);
        // List<Integer> list = new ArrayList<Integer>();
        // Collections.addAll(list, 1,1,1,3);
        // Solution.maxSum(list, 2, 2);
    }
}

/**
 * 定长滑动窗口，基础
 */
class SolutionBase{

    /**1052. 爱生气的书店老板
     * 老板没生气的时候，顾客可以在窗口外面
     */
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int s = 0, ans = 0;
        for(int i = 0; i < grumpy.length; i++){
            if(grumpy[i] == 0)
                s += customers[i];
        }
        for(int i = 0; i < customers.length ;i++){
            // in
            if(grumpy[i] == 1)
                s += customers[i];

            // left
            int left = i - minutes + 1;
            if(left < 0) continue;

            // compute
            ans = ans > s ? ans : s;

            // out
            if(grumpy[left] == 1)
                s -= customers[left];
        }
        return ans;
    }

    /*2841. 几乎唯一子数组的最大和
     * 给你一个整数数组 nums 和两个正整数 m 和 k 。
        请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
        如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
        子数组指的是一个数组中一段连续 非空 的元素序列。
     */
    public static long maxSum(List<Integer> nums, int m, int k) {
        Integer[] arr = nums.toArray(Integer[]::new);
        long s = 0, ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int i = 0; i < arr.length; i++){
            int v = arr[i];
            s += v;
            cnt.merge(v, 1, Integer::sum);

            int left = i - k + 1;
            if(left < 0) continue;

            if(cnt.size() >= m) ans = ans < s ? s : ans;

            int out = arr[left];
            int c = cnt.get(out) - 1;
            if(c <= 0) cnt.remove(out);
            else cnt.put(out, c);
            s -= out;
        }
        return ans;
    }

    /*2090. 半径为 k 的子数组平均值 */
    public static int[] getAverages(int[] nums, int k) {
            int winSize = 2 * k + 1;
            int s = 0, len = nums.length;
            int[] ans = new int[len];
            for(int i = 0; i < len; i++){
                if(i < k || i > len - k - 1){
                    ans[i] = -1;
                }
                s += nums[i];

                int left = i - winSize + 1;
                if(left < 0) continue;

                int avg = (int)(s / (winSize * 1.0));
                ans[i - k] = avg;

                int out = nums[left];
                s -= out;
            }
            return ans;
        }

    public static int[] getAveragesOptimize(int[] nums, int k){
        int n = nums.length;
        int[] avgs = new int[n];
        Arrays.fill(avgs, -1);
        long s = 0;
        for(int i = 0; i < n; i++){
            s += nums[i];
            // left = i - (2*k + 1) + 1 = i - 2*k < 0 
            // ==> left < 0 
            // ==> i < 2*k
            if(i < 2*k) continue;
            avgs[i - k] = (int)(s / (k * 2 + 1.0));
            s -= nums[i - 2*k];
        }
        return avgs;
    }

    /*643. 子数组最大平均数 I
     * 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
        请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
        任何误差小于 10^(-5) 的答案都将被视为正确答案。
     */
    public static double findMaxAverage(int[] nums, int k) {
        return 0;
    }


    /*2461. 长度为 K 子数组中的最大和
     * 给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
        子数组的长度是 k，且
        子数组中的所有元素 各不相同 。
        返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
        子数组 是数组中一段连续非空的元素序列。
     */
    public static long maximumSubarraySum(int[] nums, int k) {
        if(nums.length == 1)
            return nums[0];
        Map<Integer, Integer> counter = new HashMap<>();
        Long winSum = 0l, res = 0l;
        int index = 0;
        while(index < k){
            winSum += nums[index];
            counter.put(nums[index], counter.getOrDefault(nums[index], 0) + 1);
            index++;
        }
        if(counter.size() == k && res < winSum){
            res = winSum;
        }
        int left = 0;
        while(index < nums.length){
            counter.put(nums[index], counter.getOrDefault(nums[index], 0) + 1);
            counter.compute(nums[left], (_, v) -> (v == null || v <= 1) ? null : v - 1);
            winSum = winSum - nums[left++] + nums[index++];
            if(counter.size() == k && res < winSum){
                res = winSum;
            }
        }
        return res;
    }
    // 灵神版本
    public static long maximumSubarraySumOptimize(int[] nums, int k){
        long ans = 0, s = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            // 进入窗口
            s += nums[i];
            cnt.merge(nums[i], 1, Integer::sum);

            int left = i - k + 1;
            // 窗口大小不足k
            if(left < 0) continue;
            // 更新答案--替换为实际问题的各种统计结构
            if(cnt.size() == k) ans = ans < s ? s : ans;

            // 离开窗口
            int out = nums[left];
            s -= out;
            int c = cnt.get(out) - 1;
            if(c <= 0) cnt.remove(out);
            else cnt.put(out, c - 1);
        }
        return ans;
    }

    /*1423. 可获得的最大点数 
     * 几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
        每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
        你的点数就是你拿到手中的所有卡牌的点数之和。   
        给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
    */
    public static int maxScore(int[] cardPoints, int k) {
        if(k == cardPoints.length)
            return Arrays.stream(cardPoints).sum();
        if(k == 1)
            return Math.max(cardPoints[0], cardPoints[cardPoints.length - 1]);
        int windowSize = cardPoints.length - k;
        int sum = Arrays.stream(cardPoints).sum(), winSum = 0, min = Integer.MAX_VALUE;
        for(int i = 0; i < windowSize; i++){
            winSum += cardPoints[i];
        }
        min = Math.min(winSum, min);
        for(int right = windowSize, left = 0; right < cardPoints.length;right++,left++){
            winSum = winSum + cardPoints[right] - cardPoints[left];
            min = Math.min(winSum, min);
        }
        return sum - min;
    }
}


class Checker {

    public static void maxSumChecker(TriFunction<List<Integer>, Integer, Integer, Long> solver,int maxM,int maxK){
        maxSumChecker(solver,100000, 20, 20, 3, 10);
    }

    /**
     * 对数器：测试 maxSum
     * @param solver 你的解法 (函数式接口: (List<Integer>, m, k) -> long)
     * @param times 测试次数
     * @param maxN 最大数组长度
     * @param maxVal 元素绝对值最大值
     * @param maxM m 的最大值
     * @param maxK k 的最大值
     */
    public static void maxSumChecker(TriFunction<List<Integer>, Integer, Integer, Long> solver,
                                     int times,
                                     int maxN,
                                     int maxVal,
                                     int maxM,
                                     int maxK) {
        Random random = new Random();

        for (int t = 0; t < times; t++) {
            int n = random.nextInt(maxN) + 1;
            int k = random.nextInt(Math.max(1, Math.min(maxK, n))) + 1; // 保证 k <= n
            int m = random.nextInt(Math.max(1, Math.min(maxM, k))) + 1; // 保证 m <= k

            List<Integer> nums = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                nums.add(random.nextInt(2 * maxVal + 1) - maxVal);
            }

            long ans1 = solver.apply(nums, m, k);     // 你的解法
            long ans2 = maxSum(nums, m, k);       // 暴力解法

            if (ans1 != ans2) {
                System.out.println("❌ 出错啦！");
                System.out.println("nums = " + nums);
                System.out.println("m = " + m + ", k = " + k);
                System.out.println("solver   = " + ans1);
                System.out.println("bruteforce = " + ans2);
                return;
            }
        }
        System.out.println("✅ 全部通过！");
    }

    private static long maxSum(List<Integer> nums, int m, int k) {
        Integer[] a = nums.toArray(Integer[]::new); // 转成数组效率高

        long ans = 0;
        long s = 0;
        Map<Integer, Integer> cnt = new HashMap<>();

        for (int i = 0; i < a.length; i++) {
            // 1. 进入窗口
            s += a[i];
            cnt.merge(a[i], 1, Integer::sum); // cnt[a[i]]++

            int left = i - k + 1;
            if (left < 0) { // 窗口大小不足 k
                continue;
            }

            // 2. 更新答案
            if (cnt.size() >= m) {
                ans = Math.max(ans, s);
            }

            // 3. 离开窗口
            int out = a[left];
            s -= out;
            int c = cnt.get(out);
            if (c > 1) {
                cnt.put(out, c - 1);
            } else {
                cnt.remove(out);
            }
        }

        return ans;
    }

    /**
     * 三参数函数式接口 (Java 没内置)
     */
    @FunctionalInterface
    public interface TriFunction<T, U, V, R> {
        R apply(T t, U u, V v);
    }


    public static void getAveragesChecker(BiFunction<int[], Integer, int[]> solver, int maxKf){
        getAveragesChecker(solver, 100,2000,5000,maxKf);
    }
    /**
     * 对数器
     * @param solver 你的解法 (函数式接口)
     * @param times 测试次数
     * @param maxN 最大数组长度
     * @param maxVal 元素绝对值最大值
     * @param maxK k 的最大值
     */
    public static void getAveragesChecker(BiFunction<int[], Integer, int[]> solver,
                                          int times,
                                          int maxN,
                                          int maxVal,
                                          int maxK) {
        Random random = new Random();

        for (int t = 0; t < times; t++) {
            int n = random.nextInt(maxN) + 1; // [1, maxN]
            int k = random.nextInt(maxK + 1); // [0, maxK]

            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = random.nextInt(2 * maxVal + 1) - maxVal;
            }

            int[] ans1 = solver.apply(nums, k);   // 你的解法
            int[] ans2 = getAverages(nums, k);       // 官方题解

            if (!Arrays.equals(ans1, ans2)) {
                System.out.println("❌ 出错啦！");
                System.out.println("nums = " + Arrays.toString(nums));
                System.out.println("k = " + k);
                System.out.println("solver   = " + Arrays.toString(ans1));
                System.out.println("official = " + Arrays.toString(ans2));
                return;
            }
        }
        System.out.println("✅ 全部通过！");
    }

    /**
     * 官方题解
     */
    private static int[] getAverages(int[] nums, int k) {
        int n = nums.length;
        int[] avgs = new int[n];
        Arrays.fill(avgs, -1);
        long s = 0;
        for (int i = 0; i < n; i++) {
            s += nums[i];
            if (i < k * 2) continue;
            avgs[i - k] = (int) (s / (k * 2 + 1));
            s -= nums[i - k * 2];
        }
        return avgs;
    }
}
